{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rotating the Box"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rotateTheBox"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #旋转盒子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 的字符矩阵 <code>box</code> ，它表示一个箱子的侧视图。箱子的每一个格子可能为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'#'</code> 表示石头</li>\n",
    "\t<li><code>'*'</code> 表示固定的障碍物</li>\n",
    "\t<li><code>'.'</code> 表示空位置</li>\n",
    "</ul>\n",
    "\n",
    "<p>这个箱子被 <strong>顺时针旋转 90 度</strong> ，由于重力原因，部分石头的位置会发生改变。每个石头会垂直掉落，直到它遇到障碍物，另一个石头或者箱子的底部。重力 <strong>不会</strong> 影响障碍物的位置，同时箱子旋转不会产生<strong>惯性</strong> ，也就是说石头的水平位置不会发生改变。</p>\n",
    "\n",
    "<p>题目保证初始时 <code>box</code> 中的石头要么在一个障碍物上，要么在另一个石头上，要么在箱子的底部。</p>\n",
    "\n",
    "<p>请你返回一个<em> </em><code>n x m</code>的矩阵，表示按照上述旋转后，箱子内的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcodewithstones.png\" style=\"width: 300px; height: 150px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>box = [[\"#\",\".\",\"#\"]]\n",
    "<b>输出：</b>[[\".\"],\n",
    "      [\"#\"],\n",
    "      [\"#\"]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode2withstones.png\" style=\"width: 375px; height: 195px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>box = [[\"#\",\".\",\"*\",\".\"],\n",
    "            [\"#\",\"#\",\"*\",\".\"]]\n",
    "<b>输出：</b>[[\"#\",\".\"],\n",
    "      [\"#\",\"#\"],\n",
    "      [\"*\",\"*\"],\n",
    "      [\".\",\".\"]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode3withstone.png\" style=\"width: 400px; height: 218px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>box = [[\"#\",\"#\",\"*\",\".\",\"*\",\".\"],\n",
    "            [\"#\",\"#\",\"#\",\"*\",\".\",\".\"],\n",
    "            [\"#\",\"#\",\"#\",\".\",\"#\",\".\"]]\n",
    "<b>输出：</b>[[\".\",\"#\",\"#\"],\n",
    "      [\".\",\"#\",\"#\"],\n",
    "      [\"#\",\"#\",\"*\"],\n",
    "      [\"#\",\"*\",\".\"],\n",
    "      [\"#\",\".\",\"*\"],\n",
    "      [\"#\",\".\",\".\"]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == box.length</code></li>\n",
    "\t<li><code>n == box[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 500</code></li>\n",
    "\t<li><code>box[i][j]</code> 只可能是 <code>'#'</code> ，<code>'*'</code> 或者 <code>'.'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rotating-the-box](https://leetcode.cn/problems/rotating-the-box/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rotating-the-box](https://leetcode.cn/problems/rotating-the-box/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"#\",\".\",\"#\"]]', '[[\"#\",\".\",\"*\",\".\"],[\"#\",\"#\",\"*\",\".\"]]', '[[\"#\",\"#\",\"*\",\".\",\"*\",\".\"],[\"#\",\"#\",\"#\",\"*\",\".\",\".\"],[\"#\",\"#\",\"#\",\".\",\"#\",\".\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        def rotate(boxx):\n",
    "            str = ''.join(boxx).split('*')\n",
    "            newstr = []\n",
    "            for i in range(0, len(str)):\n",
    "                stone = ''\n",
    "                place = ''\n",
    "                for k in str[i]:\n",
    "                    if (k == '#'):\n",
    "                        stone += k\n",
    "                    elif (k == '.'):\n",
    "                        place += k\n",
    "                newstr.append(place + stone)\n",
    "            return list(\"*\".join(newstr))\n",
    "        for i in range(0,len(box)):\n",
    "            box[i]=rotate(box[i])\n",
    "        newbox=[]\n",
    "        for j in range(0,len(box[0])):\n",
    "            sbox=[]\n",
    "            for i in range(0,len(box)):\n",
    "                sbox.append(box[len(box)-1-i][j])\n",
    "            newbox.append(sbox)\n",
    "        return newbox"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        new_box = []\n",
    "        for row in box:\n",
    "            tmp = []\n",
    "            flag = 0\n",
    "            while row:\n",
    "                item = row.pop()\n",
    "                if item == \"#\":\n",
    "                    tmp.append(item)\n",
    "                elif item == \".\":\n",
    "                    flag += 1\n",
    "                else:\n",
    "                    tmp += [\".\"] * flag\n",
    "                    tmp.append(item)\n",
    "                    flag = 0\n",
    "            if flag:\n",
    "                tmp += [\".\"] * flag\n",
    "            tmp = tmp[::-1]\n",
    "            new_box.insert(0, tmp)\n",
    "        res = []\n",
    "        for i in range(len(new_box[0])):\n",
    "            tmp = []\n",
    "            for j in range(len(new_box)):\n",
    "                tmp.append(new_box[j][i])\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        new_box = []\n",
    "        for row in box:\n",
    "            tmp = []\n",
    "            flag = 0\n",
    "            while row:\n",
    "                item = row.pop()\n",
    "                if item == \"#\":\n",
    "                    tmp.append(item)\n",
    "                elif item == \".\":\n",
    "                    flag += 1\n",
    "                else:\n",
    "                    tmp += [\".\"] * flag\n",
    "                    tmp.append(item)\n",
    "                    flag = 0\n",
    "            if flag:\n",
    "                tmp += [\".\"] * flag\n",
    "            tmp = tmp[::-1]\n",
    "            new_box.append(tmp)\n",
    "        res = []\n",
    "        for i in range(len(new_box[0])):\n",
    "            tmp = []\n",
    "            for j in range(len(new_box)):\n",
    "                tmp.append(new_box[j][i])\n",
    "            res.append(tmp[::-1])\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n=len(box)\n",
    "        m=len(box[0])\n",
    "        ans=[['']*n for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            pos=m-1\n",
    "            for j in range(m-1,-1,-1):\n",
    "                if box[i][j]=='#':\n",
    "                    box[i][pos]='#'\n",
    "\n",
    "                    if pos!=j:\n",
    "                        box[i][j]='.'\n",
    "                    pos-=1\n",
    "                elif box[i][j]=='*':\n",
    "                    pos=j-1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans[j][n-1-i]=box[i][j]\n",
    "        return ans\n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: list[list[str]]) -> list[list[str]]:\n",
    "        n = len(box[0])\n",
    "        m = len(box)\n",
    "        for i in range(m):\n",
    "          barrier = n\n",
    "          for j in range(n):\n",
    "            if box[i][n-1-j] == '#':\n",
    "                box[i][n-1-j] = '.'\n",
    "                box[i][barrier-1] = '#'\n",
    "                barrier -= 1\n",
    "            elif box[i][n-j-1] == '*':\n",
    "                barrier = n-j-1\n",
    "            else:\n",
    "                continue\n",
    "            \n",
    "        res = [['.']*m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[j][m-1-i] = box[i][j]\n",
    "        return res\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    l = [[\"#\",\".\",\"#\"]]\n",
    "    res = s.rotateTheBox(l)\n",
    "    print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        \n",
    "        # Step 1: Move the stones to the rightmost possible position in each row.\n",
    "        for row in box:\n",
    "            empty = n - 1  # Position to potentially place a stone\n",
    "            for i in reversed(range(n)):\n",
    "                if row[i] == '*':\n",
    "                    empty = i - 1  # Reset position because of the obstacle\n",
    "                elif row[i] == '#':\n",
    "                    row[i], row[empty] = '.', '#'\n",
    "                    empty -= 1  # Move the empty position to the left\n",
    "        \n",
    "        # Step 2: Rotate the box\n",
    "        rotated = [['.' for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                rotated[j][m - 1 - i] = box[i][j]\n",
    "                \n",
    "        return rotated\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m=len(box)\n",
    "        n=len(box[0])\n",
    "        for i in range(m):\n",
    "            biaoji=n-1 \n",
    "            for j in range(n-1,-1,-1):\n",
    "                if box[i][j]=='*':\n",
    "                    biaoji=j-1\n",
    "                elif box[i][j]=='#':\n",
    "                    box[i][j]='.'\n",
    "                    box[i][biaoji]='#'\n",
    "                    biaoji-=1\n",
    "                else:\n",
    "                    continue\n",
    "        return list(zip(*box[::-1]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n, m = len(box), len(box[0])\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m-1, -1, -1):\n",
    "                if box[i][j] == '#':\n",
    "                    box[i][j] = '.'\n",
    "                    while j < m and box[i][j] == '.':\n",
    "                        j += 1\n",
    "                    box[i][j-1] = '#'\n",
    "        \n",
    "        res = [['.' for i in range(n)] for i in range(m)] \n",
    "\n",
    "        # print(box, res)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if box[i][j] != '.':\n",
    "                    res[j][n-i-1] = box[i][j]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, res: List[List[str]]) -> List[List[str]]:\n",
    "        for row in res :\n",
    "            stone = len(row) - 1 \n",
    "            for nums in range(len(row)-1, -1, -1):\n",
    "                if row[nums] == '#' :\n",
    "                    row[nums] = '.'\n",
    "                    row[stone] = '#'\n",
    "                    stone -= 1\n",
    "                elif row[nums] == '*' :\n",
    "                    stone = nums - 1\n",
    "        box = [list(row) for row in zip(*res[::-1])]\n",
    "        return box\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n = len(box[0]) # 每一行的长度\n",
    "\n",
    "        for l in box:\n",
    "            # 队首对应的位置\n",
    "            front_pos = n - 1\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if l[j] == \"*\":\n",
    "                    # 遇到障碍物，清空队列\n",
    "                    front_pos = j - 1\n",
    "                elif l[j] == \"#\":\n",
    "                    if front_pos > j:\n",
    "                        # 如果队列不为空，石头就会下落\n",
    "                        l[front_pos] = \"#\"\n",
    "                        l[j] = \".\"\n",
    "                        front_pos -= 1\n",
    "                    else:\n",
    "                        front_pos = j - 1\n",
    "\n",
    "        return [*zip(*box[::-1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            q = deque()\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if box[i][j] == \"*\":\n",
    "                    q.clear()\n",
    "                elif box[i][j] == \"#\":\n",
    "                    if q:\n",
    "                        pos = q.popleft()\n",
    "                        box[i][pos] = \"#\"\n",
    "                        box[i][j] = \".\"\n",
    "                        q.append(j)\n",
    "                else:\n",
    "                    q.append(j)\n",
    "        ans = [[\"\"] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[j][m - i - 1] = box[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            q = deque()\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if box[i][j] == \"*\":\n",
    "                    # 遇到障碍物，清空队列\n",
    "                    q.clear()\n",
    "                elif box[i][j] == \"#\":\n",
    "                    if q:\n",
    "                        # 如果队列不为空，石头就会下落\n",
    "                        pos = q.popleft()\n",
    "                        box[i][pos] = \"#\"\n",
    "                        box[i][j] = \".\"\n",
    "                        # 由于下落，石头变为空位，也需要加入队列\n",
    "                        q.append(j)\n",
    "                else:\n",
    "                    # 将空位加入队列\n",
    "                    q.append(j)\n",
    "\n",
    "        # 将矩阵顺时针旋转 90 度放入答案\n",
    "        \n",
    "        return [list(row)[::-1] for row in zip(*box)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, res: List[List[str]]) -> List[List[str]]:\n",
    "        for row in res :\n",
    "            stone = len(row) - 1 \n",
    "            for nums in range(len(row)-1, -1, -1):\n",
    "                if row[nums] == '#' :\n",
    "                    if stone != nums :\n",
    "                        row[stone] = '#'\n",
    "                        row[nums] = '.'\n",
    "                        print(stone)\n",
    "                    stone -= 1\n",
    "                elif row[nums] == '*' :\n",
    "                    stone = nums - 1\n",
    "        box = [list(row) for row in zip(*res[::-1])]\n",
    "        return box\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n = len(box[0]) # 每一行的长度\n",
    "        m, n = len(box), len(box[0])\n",
    "\n",
    "        for l in box:\n",
    "            # 队首对应的位置\n",
    "            front_pos = n - 1\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if l[j] == \"*\":\n",
    "                    # 遇到障碍物，清空队列\n",
    "                    front_pos = j - 1\n",
    "                elif l[j] == \"#\":\n",
    "                    if front_pos > j:\n",
    "                        # 如果队列不为空，石头就会下落\n",
    "                        l[front_pos] = \"#\"\n",
    "                        l[j] = \".\"\n",
    "                        front_pos -= 1\n",
    "                    else:\n",
    "                        front_pos = j - 1\n",
    "\n",
    "        return [*zip(*box[::-1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m = len(box)\n",
    "        n = len(box[0])\n",
    "        for i in range(m):\n",
    "            j = n - 1\n",
    "            while j >= 0:\n",
    "                if box[i][j] == '#':\n",
    "                    k = j\n",
    "                    while k + 1 < n and box[i][k + 1] == '.':\n",
    "                        k += 1 \n",
    "                    if k > j:\n",
    "                        box[i][k] = '#'\n",
    "                        box[i][j] = '.'\n",
    "                j -= 1\n",
    "        # print(box)\n",
    "        return [list(row)[::-1] for row in zip(*box)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m = len(box)\n",
    "        n = len(box[0])\n",
    "        for i in range(m):\n",
    "            j = n - 1\n",
    "            while j >= 0:\n",
    "                if box[i][j] == '#':\n",
    "                    k = j\n",
    "                    while k + 1 < n and box[i][k + 1] == '.':\n",
    "                        k += 1 \n",
    "                    if k > j:\n",
    "                        box[i][k] = '#'\n",
    "                        box[i][j] = '.'\n",
    "                j -= 1\n",
    "        # print(box)\n",
    "        return [list(row)[::-1] for row in zip(*box)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            q = deque()\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if box[i][j] == \"*\":\n",
    "                    # 遇到障碍物，清空队列\n",
    "                    q.clear()\n",
    "                elif box[i][j] == \"#\":\n",
    "                    if q:\n",
    "                        # 如果队列不为空，石头就会下落\n",
    "                        pos = q.popleft()\n",
    "                        box[i][pos] = \"#\"\n",
    "                        box[i][j] = \".\"\n",
    "                        # 由于下落，石头变为空位，也需要加入队列\n",
    "                        q.append(j)\n",
    "                else:\n",
    "                    # 将空位加入队列\n",
    "                    q.append(j)\n",
    "\n",
    "        # 将矩阵顺时针旋转 90 度放入答案\n",
    "        ans = [[\"\"] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[j][m - i - 1] = box[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, res: List[List[str]]) -> List[List[str]]:\n",
    "        for row in res :\n",
    "            stone = len(row) - 1 \n",
    "            for nums in range(len(row)-1, -1, -1):\n",
    "                if row[nums] == '#' :\n",
    "                    if stone != nums :\n",
    "                        row[stone] = '#'\n",
    "                        row[nums] = '.'\n",
    "                        print(stone)\n",
    "                    stone -= 1\n",
    "                elif row[nums] == '*' :\n",
    "                    stone = nums - 1\n",
    "        box = [list(row) for row in zip(*res[::-1])]\n",
    "        return box\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            q = deque()\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if box[i][j] == \"*\":\n",
    "                    # 遇到障碍物，清空队列\n",
    "                    q = deque()\n",
    "                elif box[i][j] == \"#\":\n",
    "                    if q:\n",
    "                        # 如果队列不为空，石头就会下落\n",
    "                        pos = q.popleft()\n",
    "                        box[i][pos] = \"#\"\n",
    "                        box[i][j] = \".\"\n",
    "                        # 由于下落，石头变为空位，也需要加入队列\n",
    "                        q.append(j)\n",
    "                else:\n",
    "                    # 将空位加入队列\n",
    "                    q.append(j)\n",
    "\n",
    "        # 将矩阵顺时针旋转 90 度放入答案\n",
    "        ans = [[\"\"] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[j][m - i - 1] = box[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        for i in range(m):\n",
    "            q = deque() # 记录空位\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if box[i][j] == \"*\":\n",
    "                    q = deque()\n",
    "                elif box[i][j] == \"#\":\n",
    "                    if q:\n",
    "                        pos = q.popleft()\n",
    "                        box[i][pos] = \"#\"\n",
    "                        box[i][j] = \".\"\n",
    "                        q.append(j)\n",
    "                else:\n",
    "                    q.append(j)\n",
    "\n",
    "        # 将矩阵顺时针旋转 90 度放入答案\n",
    "        ans = [['' for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[j][m - i - 1] = box[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n, m = len(box), len(box[0])\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = m - 1\n",
    "            while x >= 0 and box[i][x] != '.': x -= 1\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                if box[i][j] == '*':\n",
    "                    x = j - 1\n",
    "                    while x >= 0 and box[i][x] != '.': x -= 1\n",
    "                elif box[i][j] == '#':\n",
    "                    if x < j: continue\n",
    "                    box[i][x], box[i][j] = '#', '.'\n",
    "                    while x >= 0 and box[i][x] != '.': x -= 1\n",
    "        ans = [[' '] * n for _ in range(m)] \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans[j][n - 1 - i] = box[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            # 队首对应的位置\n",
    "            front_pos = n - 1\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if box[i][j] == \"*\":\n",
    "                    # 遇到障碍物，清空队列\n",
    "                    front_pos = j - 1\n",
    "                elif box[i][j] == \"#\":\n",
    "                    if front_pos > j:\n",
    "                        # 如果队列不为空，石头就会下落\n",
    "                        box[i][front_pos] = \"#\"\n",
    "                        box[i][j] = \".\"\n",
    "                        front_pos -= 1\n",
    "                    else:\n",
    "                        front_pos = j - 1\n",
    "\n",
    "        # 将矩阵顺时针旋转 90 度放入答案\n",
    "        ans = [[\"\"] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[j][m - i - 1] = box[i][j]\n",
    "        return ans\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            q = deque()\n",
    "            for j in  range(n-1,-1,-1):\n",
    "                if box[i][j] == '*':\n",
    "                    q.clear()\n",
    "                elif box[i][j] == '#':\n",
    "                    if q :\n",
    "                        box[i][q.popleft()] = '#'\n",
    "                        box[i][j] = '.'\n",
    "                        q.append(j)\n",
    "                else:\n",
    "                    q.append(j)\n",
    "        \n",
    "        ans = [[\"\"]*m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[j][m-i-1] = box[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n = len(box[0]) # 每一行的长度\n",
    "        for l in box:\n",
    "            for i in range(1, n):\n",
    "                while i > 0 and l[i - 1] == '#' and l[i] == '.':\n",
    "                    l[i - 1], l[i] = l[i], l[i - 1]\n",
    "                    i -= 1\n",
    "        return [*zip(*box[::-1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        result = [['.'] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            j1 = n-1\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if box[i][j] == '#':\n",
    "                    result[j1][~i] = '#'\n",
    "                    j1 -= 1\n",
    "                elif box[i][j] == '*':\n",
    "                    result[j][~i] = '*'\n",
    "                    j1 = j-1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        result = [[''] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                result[j][m - i - 1] = box[i][j]\n",
    "        for i in range(m):\n",
    "            start = n - 1\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if result[j][i] == '*':\n",
    "                    start = j - 1\n",
    "                elif result[j][i] == '#':\n",
    "                    result[j][i], result[start][i] = '.', '#'\n",
    "                    start -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        ans = [['.'] * m for _ in range(n)]\n",
    "        #* 遍历行\n",
    "        for i, row in enumerate(box):\n",
    "            #* 从后往前遍历列\n",
    "            cnt_stone = 0\n",
    "            start = n-1\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if box[i][j] == '*':\n",
    "                    #* 从start开始填石头\n",
    "                    k = 0\n",
    "                    while(k < cnt_stone):\n",
    "                        ans[start-k][m-i-1] = '#'\n",
    "                        k+=1\n",
    "                    ans[j][m-i-1] = '*'\n",
    "                    start = j-1\n",
    "                    cnt_stone = 0\n",
    "                elif box[i][j] == '#':\n",
    "                    cnt_stone+=1\n",
    "            k = 0\n",
    "            while(k < cnt_stone):\n",
    "                ans[start-k][m-i-1] = '#'\n",
    "                k+=1      \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        res = [[''] * m for _ in range(n)]\n",
    "        for q, row in enumerate(box):\n",
    "            nums = [i for (i, c) in enumerate(row) if c == '*']\n",
    "            if not nums:\n",
    "                c0, c1 = row.count('.'), row.count('#')\n",
    "                tmp = ['.'] * c0 + ['#'] * c1 \n",
    "            else:\n",
    "                tmp = row.copy()\n",
    "                i = 0\n",
    "                while i < n:\n",
    "                    if tmp[i] == '*':\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    j = i + 1\n",
    "                    while j < n and tmp[j] != '*':\n",
    "                        j += 1\n",
    "                    c0, c1 = row[i: j].count('.'), row[i: j].count('#')\n",
    "                    for k in range(i, j):\n",
    "                        if c0 > 0:\n",
    "                            tmp[k] = '.'\n",
    "                            c0 -= 1\n",
    "                        else:\n",
    "                            tmp[k] = '#'\n",
    "                            c1 -= 1\n",
    "                    i = j + 1\n",
    "                \n",
    "            for j in range(n):\n",
    "                res[j][m - q - 1] = tmp[j]\n",
    "                # i = 0, j = nums[0]\n",
    "                # c0, c1 = row[i: j].count('.'), row[i: j].count('#')\n",
    "                # t = ['.'] * c0 + ['#'] * c1 \n",
    "                # t += \n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n, m = len(box), len(box[0])\n",
    "        ans = [['.'] * n for _ in range(m)]\n",
    "\n",
    "        for i, r in enumerate(box):\n",
    "            for j in range(m):\n",
    "                cnt = 0\n",
    "                while j < m and r[j] != '*':\n",
    "                    if r[j] == '#':\n",
    "                        cnt += 1\n",
    "                    j += 1\n",
    "                if j < m:\n",
    "                    ans[j][n-1-i] = '*'\n",
    "                k = j - 1\n",
    "                while cnt:\n",
    "                    ans[k][n-1-i] = '#'\n",
    "                    k -= 1\n",
    "                    cnt -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        res = [['.' for _ in range(len(box))] for _ in range(len(box[0]))]\n",
    "        for row in range(len(box) - 1, -1, -1):\n",
    "            curRight = len(box[0])\n",
    "            cnt = 0\n",
    "            newCol = len(box) - 1 - row\n",
    "            #[[\"#\",\"#\",\"#\",\"*\",\".\",\".\"],\n",
    "            # [\"#\",\"#\",\"#\",\".\",\"#\",\".\"]]\n",
    "            # [[\".\",\"#\"],     [\".\",\"#\"]\n",
    "            #. [\".\",\"#\"],     [\".\",\"#\"]\n",
    "            #. [\"#\",\"#\"],     [\"#\",\"#\"]\n",
    "            #. [\"#\",\"*\"],     [\"*\",\".\"]\n",
    "            #. [\"#\",\".\"],     [\"#\",\".\"]\n",
    "            #. [\"#\",\".\"]].    [\"#\",\".\"]\n",
    "            for col in range(len(box[0]) - 1, -1, -1):\n",
    "                if box[row][col] == '*':\n",
    "                    curIdx = curRight - 1\n",
    "                    while cnt > 0:\n",
    "                        res[curIdx][newCol] = '#'\n",
    "                        curIdx -= 1\n",
    "                        cnt -= 1\n",
    "                    curRight = col\n",
    "                    res[col][newCol] = '*'\n",
    "                elif box[row][col] == '#':\n",
    "                    cnt += 1\n",
    "            curIdx = curRight - 1                    \n",
    "            while cnt > 0:\n",
    "                res[curIdx][newCol] = '#'\n",
    "                curIdx -= 1\n",
    "                cnt -= 1\n",
    "            # print(res)                \n",
    "        return res                                                                   \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        ans = [['.'] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                if box[i][j] == '*':\n",
    "                    ans[j][m-1-i] = '*'\n",
    "                    for k in range(1, count+1):\n",
    "                        ans[j-k][m-1-i] = '#'\n",
    "                    count = 0\n",
    "                elif box[i][j] == '#':\n",
    "                    count += 1\n",
    "            if count:\n",
    "                for k in range(count):\n",
    "                    ans[n-1-k][m-1-i] = '#'\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        row_length, column_length = len(box), len(box[0])\n",
    "        for row in box:\n",
    "            cur = column_length - 1\n",
    "            for column in range(column_length - 1, -1, -1):\n",
    "                val = row[column]\n",
    "                if val == '*':\n",
    "                    cur = column - 1\n",
    "                elif val == '#':\n",
    "                    row[cur], row[column] = row[column], row[cur]\n",
    "                    cur -= 1\n",
    "        return list(zip(*box[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        res = [[0 for i in range(m)] for j in range(n)]\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            l = {'.': 0, '#': 0, '*': 0}\n",
    "            for j, item in enumerate(box[i]):\n",
    "                l[item] += 1\n",
    "                if item == '*' or j == n-1:\n",
    "                    tmp += ['.'] * l['.']\n",
    "                    tmp += ['#'] * l['#']\n",
    "                    tmp += ['*'] * l['*']\n",
    "                    l = {'.': 0, '#': 0, '*': 0}\n",
    "            for j in range(n):\n",
    "                res[j][m - 1 - i] = tmp[j]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        res = [[0 for i in range(m)] for j in range(n)]\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            l = {'.': 0, '#': 0, '*': 0}\n",
    "            for j, item in enumerate(box[i]):\n",
    "                l[item] += 1\n",
    "                if item == '*' or j == n-1:\n",
    "                    tmp += ['.'] * l['.']\n",
    "                    tmp += ['#'] * l['#']\n",
    "                    tmp += ['*'] * l['*']\n",
    "                    l = {'.': 0, '#': 0, '*': 0}\n",
    "            for j in range(n):\n",
    "                res[j][m - 1 - i] = tmp[j]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m = len(box)\n",
    "        n = len(box[0])\n",
    "        ans = [['.'] * m for _ in range(n)]\n",
    "\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if box[i][j] == '#':\n",
    "                    count += 1\n",
    "                elif box[i][j] == '*':\n",
    "                    ans[j][m - 1 - i] = box[i][j]\n",
    "                    for k in range(count):\n",
    "                        ans[j - 1 - k][m - 1 - i] = '#'\n",
    "                    count = 0\n",
    "            if count:  # 没有障碍物\n",
    "                for k in range(count):\n",
    "                    ans[n - 1 - k][m - 1 - i] = '#'\n",
    "                count = 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        n, m = len(box), len(box[0])\n",
    "        ans = []\n",
    "        temp_rotate = []\n",
    "        \n",
    "        def apply_gravity(column):\n",
    "            n = len(column)\n",
    "            result = column[:]\n",
    "            i = n - 1\n",
    "            while i >= 0:\n",
    "                if result[i] == '#' and i + 1 <= n - 1 and result[i + 1] != '#':\n",
    "                    j = i + 1\n",
    "                    while j < n and result[j] == '.':\n",
    "                        j += 1\n",
    "                    result[i], result[j - 1] = result[j - 1], result[i]\n",
    "                i -= 1\n",
    "\n",
    "            return result\n",
    "        \n",
    "        for i in range(n):\n",
    "            temp_rotate.append(apply_gravity(box[i]))\n",
    "            print(i, apply_gravity(box[i]))\n",
    "        print(temp_rotate)\n",
    "        \n",
    "        for i in range(m):\n",
    "            temp = []\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                temp.append(temp_rotate[j][i])\n",
    "            ans.append(temp)\n",
    "        # print(ans)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        res = [[''] * m for _ in range(n)]\n",
    "        for q, row in enumerate(box):\n",
    "            nums = [i for (i, c) in enumerate(row) if c == '*']\n",
    "            if not nums:\n",
    "                c0, c1 = row.count('.'), row.count('#')\n",
    "                tmp = ['.'] * c0 + ['#'] * c1 \n",
    "            else:\n",
    "                tmp = row.copy()\n",
    "                i = 0\n",
    "                while i < n:\n",
    "                    if tmp[i] == '*':\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    j = i + 1\n",
    "                    while j < n and tmp[j] != '*':\n",
    "                        j += 1\n",
    "                    c0, c1 = row[i: j].count('.'), row[i: j].count('#')\n",
    "                    for k in range(i, j):\n",
    "                        if c0 > 0:\n",
    "                            tmp[k] = '.'\n",
    "                            c0 -= 1\n",
    "                        else:\n",
    "                            tmp[k] = '#'\n",
    "                            c1 -= 1\n",
    "                    i = j + 1\n",
    "                \n",
    "            for j in range(n):\n",
    "                res[j][m - q - 1] = tmp[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "      m = len(box)\n",
    "      n = len(box[0])\n",
    "      ret = [ [0] * m for _ in range(n) ]\n",
    "\n",
    "      for i in range(m):\n",
    "        l = ['.'] * n\n",
    "        nn = 0\n",
    "        for j in range(n):\n",
    "          if box[i][j] == '#':\n",
    "            nn += 1\n",
    "          elif box[i][j] == '*':\n",
    "            l[j] = '*'\n",
    "            for k in range(nn):\n",
    "              l[j - k - 1] = '#'\n",
    "            nn = 0\n",
    "        if nn > 0:\n",
    "          for k in range(nn):\n",
    "              l[n - k - 1] = '#'\n",
    "            \n",
    "        col = m - 1 - i\n",
    "        for row in range(n):\n",
    "          ret[row][col] = l[row]\n",
    "      \n",
    "      return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        res = [[None] * m for _ in range(n)]\n",
    "\n",
    "        for x in range(m):\n",
    "            l, r = n - 1, n - 1\n",
    "            c = m - x - 1\n",
    "            while r >= 0:\n",
    "                if l >= 0:\n",
    "                    if box[x][l] == '*':\n",
    "                        if r > l:\n",
    "                            for i in range(l + 1, r + 1):\n",
    "                                res[i][c] = '.'\n",
    "                        res[l][c] = '*'\n",
    "                        r = l - 1\n",
    "                    elif box[x][l] == '#':\n",
    "                        res[r][c] = '#'\n",
    "                        r -= 1\n",
    "                    l -= 1\n",
    "                else:\n",
    "                    res[r][c] = '.'\n",
    "                    r -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        stones = []\n",
    "        walls = []\n",
    "        n = len(box)\n",
    "        m = len(box[0])\n",
    "        ans = [['.' for t in range(n)]for _ in range(m) ]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if box[i][j]=='#':\n",
    "                    stones.append([j,n-i-1])\n",
    "                elif box[i][j]=='*':\n",
    "                    walls.append([j,n-i-1])\n",
    "        for x,y in stones:\n",
    "            ans[x][y] = '#'\n",
    "        for x,y in walls:\n",
    "            ans[x][y] = '*'\n",
    "        for x,y in stones:\n",
    "            tem = -1\n",
    "            for t in range(x+1,m):\n",
    "                if ans[t][y] =='*':\n",
    "                    break\n",
    "                if ans[t][y]=='.':\n",
    "                    tem = t\n",
    "            if tem>0:\n",
    "                ans[tem][y] = '#'\n",
    "                ans[x][y] = '.'\n",
    "        #print(stones,ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m = len(box)\n",
    "        n = len(box[0])\n",
    "\n",
    "        res = [[0 for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                \"\"\"\n",
    "                00 m - 1, 0\n",
    "                01 m - 2, 0\n",
    "                02 m - 3, 0\n",
    "\n",
    "                10 m - 1, 1\n",
    "                11 m - 2, 1\n",
    "                12 m - 3, 1\n",
    "                \"\"\"\n",
    "                res[j][i] = box[m - i - 1][j]\n",
    "\n",
    "        # print(res)\n",
    "        # print(res[])\n",
    "        for j in range(m):\n",
    "            for i in range(n - 2, -1 ,-1):\n",
    "                # print(i, n)\n",
    "                while i + 1 < n and res[i + 1][j] == \".\" and res[i][j] == \"#\":\n",
    "                    res[i + 1][j] = \"#\"\n",
    "                    res[i][j] = \".\"\n",
    "                    i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        res = [[0 for i in range(m)] for j in range(n)]\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            space, stone, obstacle = 0, 0, 0\n",
    "            for j, item in enumerate(box[i]):\n",
    "                if item == '.':\n",
    "                    space += 1\n",
    "                elif item == '#':\n",
    "                    stone += 1\n",
    "                else:\n",
    "                    obstacle += 1\n",
    "                if item == '*' or j == n-1:\n",
    "                    tmp += ['.'] * space\n",
    "                    tmp += ['#'] * stone\n",
    "                    tmp += ['*'] * obstacle\n",
    "                    space, stone, obstacle = 0, 0, 0\n",
    "            for j in range(n):\n",
    "                res[j][m - 1 - i] = tmp[j]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        t = []\n",
    "        for i in range(len(box[0])):\n",
    "            temp = []\n",
    "            for j in range(len(box)-1, -1, -1):\n",
    "                temp.append(box[j][i])\n",
    "            t.append(temp)\n",
    "\n",
    "        # print(t)\n",
    "\n",
    "        for i in range(len(t[0])):\n",
    "            for j in range(len(t)-1, -1, -1):\n",
    "                if t[j][i] == '#':\n",
    "                    start = [j,i]\n",
    "                    while start[0]+1<len(t) and t[start[0]+1][start[1]] == '.':\n",
    "                        t[start[0]][start[1]] = '.'\n",
    "                        t[start[0]+1][start[1]] = '#'\n",
    "                        start[0] += 1\n",
    "        \n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        y = len(box)\n",
    "        x = len(box[0])\n",
    "        res = [[\".\" for i in range(y)] for j in range(x)]\n",
    "        for i in range(y):\n",
    "            for j in range(x):\n",
    "                res[j][y-1-i] = box[i][j]\n",
    "        print(res)\n",
    "        for i in range(x-2, -1, -1):\n",
    "            #print(res[i])\n",
    "            for j in range(y):\n",
    "                if res[i][j] == \"#\":\n",
    "                    tmpi = i \n",
    "                    tmpj = j\n",
    "                    for k in range(i, x):\n",
    "                        if res[k][j] == \"*\":\n",
    "                            break\n",
    "                        if res[k][j] == \".\":\n",
    "                            res[tmpi][tmpj] = \".\"\n",
    "                            res[k][j] = \"#\"\n",
    "                            tmpi = k\n",
    "                        \n",
    "        print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        move_r_box = []\n",
    "\n",
    "        def generate_row(empty_cnt, stone_cnt):\n",
    "            return '.' * empty_cnt + '#' * stone_cnt\n",
    "\n",
    "        for row in box:\n",
    "            current = ''\n",
    "            stone_cnt = 0\n",
    "            empty_cnt = 0\n",
    "            for idx, ii in enumerate(row):\n",
    "                if ii == '*':\n",
    "                    current += generate_row(empty_cnt, stone_cnt) + '*'\n",
    "                    stone_cnt = 0\n",
    "                    empty_cnt = 0\n",
    "                elif ii == '#':\n",
    "                    stone_cnt += 1\n",
    "                elif ii == '.':\n",
    "                    empty_cnt += 1\n",
    "            \n",
    "            current += generate_row(empty_cnt, stone_cnt)\n",
    "            move_r_box.append(current)\n",
    "        \n",
    "        move_r_box = move_r_box[::-1]\n",
    "        ans = []\n",
    "        for ii in range(len(move_r_box[0])):\n",
    "            row = []\n",
    "            for jj in range(len(move_r_box)):\n",
    "                row.append(move_r_box[jj][ii])\n",
    "            ans.append(row)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1861 lang=python\n",
    "#\n",
    "# [1861] 旋转盒子\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution(object):\n",
    "    def rotateTheBox(self, box):\n",
    "        \"\"\"\n",
    "        :type box: List[List[str]]\n",
    "        :rtype: List[List[str]]\n",
    "        \"\"\"\n",
    "        col = len(box)\n",
    "        row = len(box[0])\n",
    "        self.new_box = [[\".\"] * col for i in range(row)]\n",
    "        for i in range(col):\n",
    "            for j in range(row):\n",
    "                self.new_box[j][col -1 - i] = box[i][j]\n",
    "        \n",
    "        for now_location in range(col):\n",
    "            point = row-1\n",
    "            while point >=0 and (self.new_box[point][now_location] != \".\"):\n",
    "                point -= 1\n",
    "            if point <0:\n",
    "                continue\n",
    "            i = point\n",
    "            while i > -1:\n",
    "                if self.new_box[i][now_location] == \"#\":\n",
    "                    self.swap(i,now_location,point)\n",
    "                    point -= 1\n",
    "                elif self.new_box[i][now_location] == \"*\":\n",
    "                    point = i\n",
    "                    while point >=0 and (self.new_box[point][now_location] != \".\"):\n",
    "                        point -= 1\n",
    "                        i -= 1\n",
    "                i -= 1\n",
    "        \n",
    "        return self.new_box\n",
    "\n",
    "    \n",
    "    def swap(self,i,now_location,point):\n",
    "        a = self.new_box[i][now_location]\n",
    "        self.new_box[i][now_location] = self.new_box[point][now_location]\n",
    "        self.new_box[point][now_location] = a\n",
    "\n",
    "# @lc code=end\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        ans = []\n",
    "        for a in box:\n",
    "            tmp = []\n",
    "            l = {'.': 0, '#': 0, '*': 0}\n",
    "            for i, item in enumerate(a):\n",
    "                l[item] += 1\n",
    "                if item == '*' or i == n-1:\n",
    "                    tmp += ['.'] * l['.']\n",
    "                    tmp += ['#'] * l['#']\n",
    "                    tmp += ['*'] * l['*']\n",
    "                    l = {'.': 0, '#': 0, '*': 0}\n",
    "            ans.append(tmp)\n",
    "\n",
    "        res = [[0 for i in range(m)] for j in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[j][m - 1 - i] = ans[i][j]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        tmp = []\n",
    "        for row in box:\n",
    "            new = []\n",
    "            n = 0\n",
    "            for x in row[::-1]:\n",
    "                if x == '.':\n",
    "                    n += 1\n",
    "                elif x == '#':\n",
    "                    new.append('#')\n",
    "                else:\n",
    "                    new += ['.'] * n \n",
    "                    new.append('*')\n",
    "                    n = 0\n",
    "            if n:\n",
    "                new += ['.'] * n\n",
    "            tmp.append(new[::-1])\n",
    "        res = []\n",
    "        for i in range(len(box[0])):\n",
    "            t = []\n",
    "            for j in range(len(box)):\n",
    "                t.insert(0, tmp[j][i])\n",
    "            res.append(t)\n",
    "        return res\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:\n",
    "        m, n = len(box), len(box[0])\n",
    "        ans = []\n",
    "        for a in box:\n",
    "            tmp = []\n",
    "            l = {'.': 0, '#': 0, '*': 0}\n",
    "            for i, item in enumerate(a):\n",
    "                l[item] += 1\n",
    "                if item == '*' or i == n-1:\n",
    "                    tmp += ['.'] * l['.']\n",
    "                    tmp += ['#'] * l['#']\n",
    "                    tmp += ['*'] * l['*']\n",
    "                    l = {'.': 0, '#': 0, '*': 0}\n",
    "            ans.append(tmp)\n",
    "\n",
    "        res = [[0 for i in range(m)] for j in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[j][m - 1 - i] = ans[i][j]\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
